With ever-increasing popularity of low cost wireless sensor networks, the deployment of such networks in an increasing number of applications is becoming feasible. Wireless sensing and monitoring, resource tracking and management, environmental monitoring, defense and security related applications are only a few domains that offer a wide-ranging market for wireless sensor networks.
Many applications need the locations of the sensors to make sensor data meaningful. Given the fact that sensors are very low-cost devices, sensors typically do not include a global positioning system (GPS). Moreover, many sensors may operate in areas where GPS may not be effective or feasible, e.g., inside buildings and in urban environments.
A number of method are know for measuring two-way time of arrival of ranging signals, including arrival data fusion, time difference of arrival data fusion and angle of arrival data fusion. For a 2D location, at least three sensors are needed, and more for a 3D location.
Distances r between the nodes can be used to estimate their locations. A target node t estimates distances to anchor nodes n at know locations by solving{circumflex over (r)}1t2=(x1−xt)2+(y1−yt)2 {circumflex over (r)}2t2=(x2−xt)2+(y2−yt)2 {circumflex over (r)}nt2=(xN−xt)2+(yN−yt)2  (1)
A common way to solve these equations uses an over-determined non-linear system of equations, Sayed et al., “Network-based wireless location: challenges faced in developing techniques for accurate wireless location information,” IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 24-40). Rearranging terms, and assuming that target node 1 is at an origin (x1/y1)=(0,0) without losing generality, these equations can be expressed in a matrix form as
                                          Hx            =            b                    ,                                          ⁢          where                ⁢                                  ⁢                              H            =                          [                                                                                          x                      2                                                                                                  y                      2                                                                                                                                  x                      3                                                                                                  y                      3                                                                                                            ⋯                                                        ⋯                                                                                                              x                      N                                                                                                  y                      N                                                                                  ]                                ⁢                                          ,                                          ⁢                      b            =                                          1                2                            ⁡                              [                                                                                                                              x                          2                          2                                                +                                                  y                          2                          2                                                -                                                                              r                            ^                                                                                2                            ⁢                            t                                                    2                                                +                                                                              r                            ^                                                                                1                            ⁢                            t                                                    2                                                                                                                                                                                                  x                          3                          2                                                +                                                  y                          3                          2                                                -                                                                              r                            ^                                                                                3                            ⁢                            t                                                    2                                                +                                                                              r                            ^                                                                                1                            ⁢                            t                                                    2                                                                                                                                                                                                                                                                                                                                                  x                          N                          2                                                +                                                  y                          N                          2                                                -                                                                              r                            ^                                                    Nt                          2                                                +                                                                              r                            ^                                                                                1                            ⁢                            t                                                    2                                                                                                                    ]                                                    ⁢                                  ⁢                                  ⁢        and        ⁢                                  ⁢                  x          =                                    [                                                                                          x                      t                                                                                                                                  y                      t                                                                                  ]                        .                                              (        2        )            
As shown in FIG. 2, a conventional data restructuring unit 240 takes the coordinates of the locations of the anchor nodes and the measured ranges {210, 220, 230}, and determines H and b. Then, the initial position estimator 250 uses H and b to determine the initial target location using:
                                                        x              ^                                      (              0              )                                =                                    [                                                                                                                  x                        ^                                            t                                              (                        0                        )                                                                                                                                                                                y                        ^                                            t                                              (                        0                        )                                                                                                        ]                        =                                                            (                                      H                    ⁢                                                                                  ⁢                                                                                           T                                            ⁢                      H                                                        )                                                  -                  1                                            ⁢              H              ⁢                                                          ⁢                                                                   T                                ⁢                b                                                    ,                            (        3        )            where T is a transpose operator, and “^” indicates an estimate.
The initial location estimate {circumflex over (X)}(0) 251 is used to initialize an objective function 270
                                          J            ⁡                          (                                                                    x                    ^                                    t                                ,                                                      y                    ^                                    t                                            )                                =                      arg            ⁢                                                  ⁢                                          min                                                      x                    t                                    ,                                      y                    t                                                              ⁢                              (                                                      ∑                                          i                      =                      1                                        N                                    ⁢                                                                          ⁢                                                            1                                              σ                        it                        2                                                              ⁢                                                                  (                                                                                                            r                              ^                                                        it                                                    -                                                                                                                                                                                                                                                                        (                                                                                                                              x                                            i                                                                                    -                                                                                      x                                            t                                                                                                                          )                                                                            2                                                                        +                                                                                                                                                                                                                                                                          (                                                                                                                        y                                          i                                                                                -                                                                                  y                                          t                                                                                                                    )                                                                        2                                                                                                                                                                                                      )                                            2                                                                      )                                                    ,                            (        4        )            where a function max returns a maximum value, and σit is the variance of the multiple range measurements between the target and anchor nodes.
After obtaining an initial estimate for the target location, a numerical search method can be used, e.g., gradient descent or a Gauss-Newton approximation. The search procedure 260 searches for the global minimum of the cost function 270 to estimate x.
Unreliable ranges may degrade accuracy of the location estimate, because those measurements are embedded in b. Therefore, unreliable ranges need to be eliminated. In addition, the computational complexity in computing the inverse of H in Equation (3) is high, when the number of anchors is greater than three.